package sort;

import java.util.Stack;

public class QuickSort {
	
	
	//1.双指针法
	
	//first: <x的边界，即该处的值>=x
	//last:  >x的边界，即该处的值<=x
	//=>结合划分，最终一定有  arr[first]=arr[last]=x，且[first,last]表示均为x的部分
	public static int first,last;
	//对区间[l,r]内的元素进行划分，划分为三部分 <x   ==x    >x 并返回==x部分的位置
	public static void partion1(int[] array,int l,int r,int target) {
		 first=l;  //<x的边界
		 last=r;   //>x的边界
		 int i=l;
		 while(i<=r&&i<=last) {
			 //1.如果 arr[i]<x  => 交换i和first处的值，i++,first++;
			 if(array[i]<target) {
				 Swap.swap(array, first++, i++);
			 }
			 //2.如果 arr[i]>x  => 交换i和last处的值，last--,i不变，因为不知道
			 //交换后的arr[i]的值属于哪部分
			 else if(array[i]>target) {
				 Swap.swap(array, last--, i);
			 }
			 //3.如果arr[i]==x  => i++
			 else {
				 i++;
			 }
		 }	
	}
	//递归过程本质是： 先序遍历(中左右)
	public static void quickSort1(int[] array,int l,int r) {
		if(l>=r) {
			return ;
		}
		int x=array[l];  //选取第一个元素作为轴元素(可改进)
		//该函数结束，使得[l,r]分为三部分： 1.[l,first)<x  2.[first,last]=x 3.(last,r]>x
		partion1(array,l,r,x);
		//防止全局变量被覆盖
		int left=first;
		int right=last;
		quickSort1(array,l,left-1);
		quickSort1(array,right+1,r);
	}
	
	
	 //2.挖坑法
	 public static int partion2(int[] array,int l,int r) {
		 //每次选第一个元素作为坑
		 int pivot=array[l];
		 int left=l,right=r;
		 while(left<right) {
			 //必须加上left<right,因为不加可能即使left>right也不会停止
			 
			 //向右找比坑小的元素，找到停止并将小的放到left处
			 while(left<right&&pivot<=array[right]) {
				 right--;
			 }
			 //向右找比坑大的元素，找到停止并将大的放到right处
			 array[left]=array[right];
			 
			 while(left<right&&pivot>=array[left]) {
				 left++;
			 }
			 array[right]=array[left];
		 }
		 //全部找完,left即为坑的位置
		 array[left]=pivot;
		 //返回坑的位置
		 return left;
	 }
	 public static void quickSort2(int[] array,int l,int r) {
		 if(l>=r) {
			 return ;
		 }
		 int pivot=partion2(array,l,r);
		 //坑左边找新坑
		 quickSort2(array, l, pivot-1);
		 //坑右边找新坑
		 quickSort2(array, pivot+1, r);
	 }
	
	 
	 
	 //3.Hoare版本
	 public static int partion3(int[] array,int l,int r) {
		 int left=l,right=r;
		 int ret=array[left];
		 while(left<right) {
			 //往右找小，找到停止
			 while(left<right&&ret<=array[right]) {
				 right--;
			 }
			 //往左找大，找到停止
			 while(left<right&&ret>=array[left]) {
				 left++;
			 }
			 //保证 左<轴元素<右 =》交换两个数据
			 Swap.swap(array, left, right);
		 }
		 //l的位置即轴元素原来在的位置，交换位置
		 Swap.swap(array, left, l);
		 //返回轴元素的最终位置
		 return left;
	 }
	 public static void quickSort3(int[] array,int l,int r) {
		 if(l>=r) {
			 return ;
		 }
		 //获取轴元素在排好序后的下标
		 int index=partion3(array,l,r);
		 //对轴元素的左侧继续取轴
		 quickSort3(array,l,index-1);
		 //对轴元素的右侧继续取轴
		 quickSort3(array,index+1,r);
	 }
	 
	 
	 
	 //4.快排非递归实现(快排本质就是树的后序遍历，即后续遍历的非递归实现)
	  public static void quickSortNonR(int[] array) {
		  int start=0,end=array.length-1;
		  Stack<Integer> s=new Stack<>();
		  int pivot=partion2(array,start,end);
		  
		  //将接下来进行处理的区间端点入栈且只要区间长度>=2才可以入栈
		  if(start+1<pivot) {
			  s.push(start);
			  s.push(pivot-1);
		  }
		  //将接下来进行处理的区间端点入栈且只要区间长度>=2才可以入栈
		  if(end-1>pivot) {
			  s.push(pivot+1);
			  s.push(end);
		  }
		  //只要栈不为空，就对数组进行不断划分
		  while(!s.isEmpty()) {
			  end=s.pop();
			  start=s.pop();
			  pivot=partion2(array,start,end);
			  
			  if(start+1<pivot) {
				  s.push(start);
				  s.push(pivot-1);
			  }
			  
			  if(end-1>pivot) {
				  s.push(pivot+1);
				  s.push(end);
			  }
		  }
	  }
	 
	public static void main(String[] args) {
		int[] arr=new int[]{9,8,5,7,6,9,5,4,2,3,2,1,1,4};
		quickSortNonR(arr);
		for(int x:arr) 
			System.out.print(x+" ");
	}
}
